package pers.qianyu.month_202101.date_20210122;

/**
 * 面试题 08.03. 魔术索引
 * https://leetcode-cn.com/problems/magic-index-lcci/
 *
 * @author mizzle rain
 * @date 2021-01-22 12:56
 */
public class FindMagicIndex {
    // 基本做法
    public int findMagicIndex0(int[] nums) {
        int len = nums.length;
        if (len == 0) return -1;
        for (int i = 0; i < len; i++) {
            if (nums[i] == i) return i;
        }
        return -1;
    }

    // 跳跃法
    public int findMagicIndex(int[] nums) {
        int len = nums.length;
        if (len == 0) return -1;
        for (int i = 0; i < len; ) {
            if (nums[i] == i) return i;
            i = Math.max(i + 1, nums[i]);
        }
        return -1;
    }
}
